#include <algorithm>

void FB(Graph<int> &gr, int st){
	int i, j;
	std::vector<int> distance(gr.size(), INT_MAX);
	std::vector<std::tuple<int, int, int>> edges;
	for (i = 0; i< gr.size(); i++){ // получаем массив ребер <откуда, куда, вес>
		std::vector<std::tuple<std::shared_ptr<Vertex<int>>, int, bool>> vert_edges = gr.get_vertex(i).get_edges();
		for (j = 0; j < vert_edges.size(); j++)
			edges.push_back(std::make_tuple(i, (*(std::get<0>(vert_edges[j]))).get_id(), std::get<1>(vert_edges[j])));
	}
	distance[st] = 0;
	int x;
	for (i = 0; i<gr.size(); ++i) {
		x = -1; // если на последней итерации получим не -1, то был отрицательный цикл
		for (j = 0; j<edges.size(); ++j)
		if (distance[std::get<0>(edges[j])] < INT_MAX)
		if (distance[std::get<1>(edges[j])] > distance[std::get<0>(edges[j])] + std::get<2>(edges[j])) {
			distance[std::get<1>(edges[j])] = std::max(-INT_MAX, distance[std::get<0>(edges[j])] + std::get<2>(edges[j]));
			x = std::get<1>(edges[j]);
		}
	}
	try{
		if (x != -1)
			throw std::exception("Negative_cycle");
		for (i = 1; i < gr.size(); i++)
		if (distance[i] != INT_MAX) // вывод как в условии
			std::cout << distance[i] << std::endl; 
		else
			std::cout << 30000 << std::endl;
	}
	catch (std::exception e){
		std::cerr << e.what();
	}
}

void start_FB(){
	int N, M;
	int st;
	std::cin >> N >> M;
	N++;
	Graph<int> gr = Graph<int>();
	gr.set_size(N);
	int f, t, w;
	for (int i = 0; i < M; i++){
		std::cin >> f >> t >> w;
		gr.add_edge(f, t, w);
	}
	st = 1;
	gr.reiterate();
	FB(gr, st);
}